A communication network is a geographically distributed collection of nodes interconnected by communication links and segments for transporting communications (e.g., data, voice, video) between communication units (end nodes), such as personal computers, certain telephones, personal digital assistants (PDAs), video units and the like. Many types of communication networks are available, with the types ranging from local area networks (LANs) to wide area networks (WANs). LANs typically connect nodes over dedicated private communications links located in the same general geographical location, such as a building or campus. WANs, on the other hand, typically connect large numbers of geographically dispersed nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols, such as the Transmission Control Protocol/Internet Protocol (TCP/IP). In this context, a protocol is a set of rules defining how the nodes interact with each other.
A communication network may comprise a series of intermediate nodes (e.g., routers) that are configured to carry communications through the network to the end nodes. A router is a type of intermediate node that is typically configured to “route” data, such as packets, between various nodes in the network. Routing is performed at layer-3 (L3), which is the network layer of the Open Systems Interconnection Reference Model (OSI-RM).
Routers often maintain forwarding information bases (FIBs) which are typically configured to hold routing information (e.g., L3 addresses) and interface information that the router uses to determine how to forward the data in order to reach its destination. A typical FIB is a data structure organized as a table containing one or more entries wherein each entry contains an L3 destination address of a destination node and interface information about an interface on the router through which the destination node may be reached. Data (e.g., a data packet) containing a destination address that matches a destination address of an entry in the FIB are forwarded by the router to the interface specified by the matching entry for transfer on a path to the destination node.
A router may execute one or more routing protocols that enable the router to route packets and exchange routing information with other routers in the network. The routers often use this information to configure (e.g., compute) their FIBs. The routing protocols may include distance-vector protocols, such as the Routing Information Protocol (RIP), or link-state protocols, such as the Intermediate-System-to-Intermediate-System (IS-IS) protocol and the Open Shortest Path First (OSPF) protocol.
Routing information is typically exchanged between the routers in the form of advertisement messages. For example, nodes executing the IS-IS protocol exchange routing information using an advertisement message called a Link State Packet (LSP). Likewise, nodes executing the OSPF protocol exchange routing information using an advertisement message called a Link State Advertisement (LSA). A router that acquires an advertisement message may use information contained therein to update its FIB.
Some communication networks employ Multiprotocol Label Switching (MPLS) technology to deliver data packets across a communication network along paths from sources to destinations. MPLS is a well-known technology that provides for the efficient designation, routing, forwarding and switching of flows of traffic (data flows) through a communication network. Data traffic associated with the flows is carried through the network via paths called label-switched paths (LSPs). An LSP is a path in a communication network that is defined by a sequence of labels at each and every node along the path from a source to a destination. LSPs may be established prior to data transmission or upon detection of a certain flow of data. MPLS is described in E. Rosen, et al., Request for Comments (RFC) 3031, “Multiprotocol Label Switching Architecture,” Internet Engineering Task Force (IETF), January 2001, pages 1-61.
Networks that support MPLS are often referred to as MPLS networks. In an MPLS network, MPLS packets are typically processed by special routers called label switching routers (LSRs) and label edge routers (LERs). Both LSRs and LERs participate in the establishment of LSPs as well as the high-speed switching of data traffic based on the established LSPs. LERs are routers which operate at the edge of an MPLS network and provide access to the network. LSRs are often high-speed routers that comprise the core of MPLS networks and switch MPLS packets along paths between the LERs.
MPLS uses labels which determine how the traffic is switched (forwarded) along an LSP. The labels typically reside between the layer-2 (L2) and L3 headers of MPLS packets. A label typically comprises a label field, an experimental field, an “S” field and a time to live (TTL) field. The label field holds the value of the label. The experimental field holds a value that is reserved for experimental use. In some MPLS implementations, this field holds a value that represents a class-of-service (CoS) associated with the label. The “S” field holds a value that indicates whether or not the label is at the bottom of a stack of labels (described further below) that are contained in the MPLS packet. The TTL field indicates a “time-to-live” value associated with the label.
An MPLS packet contains a stack of one or more labels which is sometimes referred to as the packet's MPLS label stack. An MPLS label stack comprises a bottom label and optionally one or more additional labels. The “S” bit for the bottom label is typically set to a value of one to indicate the label is at the bottom of the stack. The “S” bits for the additional labels are typically set to zero to indicate these labels are not at the bottom of the stack.
Each label in an MPLS packet is associated with a forwarding equivalence class (FEC). An FEC indicates how a packet is treated with regards to being forwarded. Packets associated with the same FEC are generally treated the same with regard to forwarding the packets to their destination. In other words, an FEC describes a set of packets which may be forwarded the same way; that is, they may be bound to the same MPLS label.
Labels are usually only significant at a particular local node. Thus, for a particular FEC, the label associated with the FEC may be different at different nodes. For example, a node may associate a label value of “45” to a particular FEC whereas another node may associate a label value of “52” with the same FEC.
As noted above, LSPs are configured to carry data flows of traffic. A data flow refers to a flow of data (e.g., data packets) that travels from a particular source to a particular destination. Data packets that comprise a data flow typically have the same source and same destination addresses. In MPLS, a data flow travels on an LSP hop-by-hop through the network. At each node along the LSP, the top label on the MPLS label stack of an MPLS packet is typically used to determine which path the packet takes to the next hop along the LSP.
In some instances, there may be two paths that packets belonging to different flows may take to reach the next hop. Here, a load balancing technique may be employed to “load balance” the traffic from various data flows across the two paths. One commonly used technique for balancing MPLS traffic across multiple paths is the IP Equal Cost Multiple Path (ECMP) load balancing technique.
IP ECMP is geared towards load balancing IP-type packets that belong to multiple flows that may take multiple paths to their next hop. Load balancing is typically accomplished by selecting one of the paths based on a source and destination address contained in the packet and forwarding the packet on the selected path. In a typical IP ECMP implementation, the selected path is chosen by hashing some combination of source address and destination address bits contained in a packet's IP header which is typically contained a payload portion of the packet when viewed at the data link layer. The path for the packet is then selected based on the results of the hash.
Some IP ECMP implementations check the traffic in an attempt to ensure it is indeed IP-based traffic before applying the IP ECMP technique. Here, the first nibble of the packet's network layer header is typically examined to determine if it contains a value of “4” or “6” which indicate the packet is an IP version 4 (IPv4)-type packet and an IP version 6 (IPv6)-type packet, respectively. If the packet contains either of these values in the first byte of the packet's network layer header, the packet is assumed to be an IP packet and IP ECMP is applied to determine the packet's path to its next hop.